Function Categories
Polynomials
p ( x ) p(x) p ( x ) is a polynomial of degree n n n , n = 0 , 1 , 2 , ⋯ n=0,1,2,\cdots n = 0 , 1 , 2 , ⋯ is a function of the form
p ( x ) = a n x n + a n − 1 x n − 1 + ⋯ + a 1 x + a 0 p(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots +a_1x + a_0 p ( x ) = a n x n + a n − 1 x n − 1 + ⋯ + a 1 x + a 0 d o m ( p ) = R dom(p) = \Bbb{R} d o m ( p ) = R
a i a_i a i = coefficients a n ≠ 0 a_n\ne 0 a n = 0 = lead coefficient a 0 a_0 a 0 = constant term
If a i ∈ Z a_i\in\Bbb{Z} a i ∈ Z , we say p ( x ) p(x) p ( x ) has integer coefficients and we write
Z [ x ] = \Set of all polynomial with integer coefficient \Bbb{Z}[x]=\Set{\text{ of all polynomial with integer coefficient }} Z [ x ] = \Set of all polynomial with integer coefficient
Similarly we define Q [ x ] , R [ x ] , C [ x ] \Bbb{Q}[x], \Bbb{R}[x], \Bbb{C}[x] Q [ x ] , R [ x ] , C [ x ] as the sets of all polynomials with rational, real, or complex coefficients respectively
If a n = 1 a_n=1 a n = 1 , we call p ( x ) p(x) p ( x ) a monic polynomial
The Fundamental Theorem of Algebra
bdg-info The Fundamental Theorem of Algebra
A polynomial of degree n has exactly n complex zeroes, counting multiplicity
x 0 x_0 x 0 is a zero of p ( x ) p(x) p ( x ) iff p ( x 0 ) = 0 p(x_0)=0 p ( x 0 ) = 0 ie: a solution of the equation p ( x ) = 0 p(x)=0 p ( x ) = 0
The multiplicity of x 0 x_0 x 0 is the largest value of k k k such that p ( x ) = ( x − x 0 ) k q ( x ) p(x)=(x-x_0)^kq(x) p ( x ) = ( x − x 0 ) k q ( x ) where q ( x 0 ) ≠ 0 q(x_0)\ne 0 q ( x 0 ) = 0
( x − x 0 ) k (x-x_0)^k ( x − x 0 ) k is called a linear factor of p ( x ) p(x) p ( x ) of degree k k k
bdg-secondary Fact If p ( x ) ∈ R [ x ] p(x)\in\Bbb{R}[x] p ( x ) ∈ R [ x ] , p p p has real numbers as coefficients, then p ( x ) p(x) p ( x ) can be factored into a product of linear terms (possibly repeated) if irreducible quadratic terms (possibly repeated)
An irreducible quadratic has the form a x 2 + b x + c = 0 ax^2+bx+c=0 a x 2 + b x + c = 0 when b 2 − 4 a c < 0 b^2-4ac<0 b 2 − 4 a c < 0
bdg-info Quadratic Formula if a x 2 + b x + c = 0 ax^2+bx+c=0 a x 2 + b x + c = 0 iff
x = − b ± b 2 − 4 a c 2 a x = \frac{-b\pm\sqrt{b^2-4ac}}{2a} x = 2 a − b ± b 2 − 4 a c Example
Let p ( x ) = ( 2 x − 1 ) 4 ( x + 3 ) 2 ( x 2 − 4 x + 13 ) 2 p(x)=(2x-1)^4(x+3)^2(x^2-4x+13)^2 p ( x ) = ( 2 x − 1 ) 4 ( x + 3 ) 2 ( x 2 − 4 x + 13 ) 2
d e g ( p ) = 4 + 2 + 4 = 10 deg(p)= 4+2+4=10 d e g ( p ) = 4 + 2 + 4 = 10
All the multiplicities of the zeros must add up to 10
bdg-danger Real Zeroes
x = 1 / 2 x=1/2 x = 1/2 multiplicity 4
x = − 3 x=-3 x = − 3 multiplicity 2
bdg-danger Complex Zeroes
x^2-4x+13&(x-2)^2-4+13\\
b^2-4ac=16-52<0&=(x-2)^2+9=0\\
iff\ (x-2)^2&=-9\\
x-2&=\pm\sqrt{-9}=\pm 3i\\
x&= 2\pm 3i\\
x = 2 + 3 i x=2+3i x = 2 + 3 i multiplicity 2
x = 2 − 3 i x=2-3i x = 2 − 3 i multiplicity 2
bdg-secondary Recall r ( x ) = p ( x ) / q ( x ) r(x)=p(x)/q(x) r ( x ) = p ( x ) / q ( x ) where p p p , q q q are polynomials is called a rational function d o m ( r ) = \Set x ∈ R ∣ q ( x ) ≠ 0 dom(r)=\Set{x\in\Bbb{R}\mid q(x)\ne 0} d o m ( r ) = \Set x ∈ R ∣ q ( x ) = 0
Rational Functions
Basic Rational Functions
The simplest rational function is f ( x ) = 1 x f(x) = \frac{1}{x} f ( x ) = x 1 , d o m ( 1 x ) = \Set x ∈ R ∣ x ≠ 0 dom(\frac{1}{x})=\Set{x\in\Bbb{R}\mid x\ne 0} d o m ( x 1 ) = \Set x ∈ R ∣ x = 0
Features of Graph
Has vertical and horizontal asymptote
Horizontal Asymptotes
This a reflection of the fact that:
lim x → 0 ± 1 x = ± ∞ \lim_{x\to 0^\pm}\frac{1}{x}=\pm\infty x → 0 ± lim x 1 = ± ∞ That is, the closer to x = 0 x=0 x = 0 , f ( x ) = 1 x f(x)=\frac{1}{x} f ( x ) = x 1 it becomes larger and larger that is f becomes unbounded
Vertical Asymptotes
This a reflection of the fact that:
lim x → ∞ ± 1 x = ± ∞ \lim_{x\to\infty^\pm}\frac{1}{x}=\pm\infty x → ∞ ± lim x 1 = ± ∞ That is, the higher the absolute value of x x x is, the closer 1 x \frac{1}{x} x 1 is to 0
General Rational Functions
r ( x ) = p ( x ) g ( x ) r(x)=\frac{p(x)}{g(x)} r ( x ) = g ( x ) p ( x ) 3 types of asymptotes
Vertical Asymptotes - occur at x = a x=a x = a when g ( a ) = 0 g(a)=0 g ( a ) = 0
Horizontal Asymptotes - occur when lim x → ± ∞ \lim_{x\to\pm\infty} lim x → ± ∞ is a finite number. This means, in particular d e g ( p ) ≤ d e g ( g ) deg(p)\le deg(g) d e g ( p ) ≤ d e g ( g ) and if lim x → ± ∞ \lim_{x\to\pm\infty} lim x → ± ∞ , the horizontal asymptote us given by y = a y=a y = a
Skew or Slant Asymptotes - occurs when d e g ( p ) = d e g ( g ) + 1 deg(p)=deg(g) + 1 d e g ( p ) = d e g ( g ) + 1
Inverse Rational Functions
Certain types of rational functions, called linear fractional transformations , have inverse functions
These L.F.T's are those rational functions of the form:
f ( x ) = a x + b c x + d where a,b,c,d are real constants f(x)=\frac{ax+b}{cx+d}\ \ \text{ where a,b,c,d are real constants} f ( x ) = c x + d a x + b where a,b,c,d are real constants We can show that these functions are 1-1 on d o m ( f ) = \Set x ∈ R ∣ x ≠ − d c ( c ≠ 0 ) dom(f)=\Set{x\in\Bbb{R}\mid x\ne\frac{-d}{c}}\ (c\ne 0) d o m ( f ) = \Set x ∈ R ∣ x = c − d ( c = 0 )
and we find thier inverse function f − 1 ( x ) f^{-1}(x) f − 1 ( x ) in order to find r a n g e ( f ) range(f) r an g e ( f ) since:
dom(f^{-1})&=\ range(f)\\
dom(f)&=\ range(f^{-1})\\
Illustrate by example
let below be a real function
f ( x ) = 2 x + 1 x − 1 f(x)=\frac{2x+1}{x-1} f ( x ) = x − 1 2 x + 1
find d o m ( f ) dom(f) d o m ( f )
dom(f)
&=\Set{x\in\Bbb{R}\mid x-1\ne 0}\\
&=\Set{x\in\Bbb{x}\mid x\ne 1}\\
&= \Bbb{R}\backslash\Set{1}\\
&=(-\infty,1)\cup (1,+\infty)\\
Show that f f f is 1-1 on it's domain
bdg-success Solution
let x 1 , x 2 ∈ d o m ( f ) x_1,x_2\in dom(f) x 1 , x 2 ∈ d o m ( f ) and suppose f ( x 1 ) = f ( x 2 ) f(x_1)=f(x_2) f ( x 1 ) = f ( x 2 ) Then
\frac{2x_1+1}{x_1-1}&=\frac{2x_2+1}{x_2-1}\\
(2x_1+1)(x_2-1)&=(2x_2+1)(x_1-1)\\
2x_1x_2-2x_1+x_2-1&=2x_1x_2-2x_2+x_2-1\\
3x_2&=3x_1\\
x_2&=x_1\\
Therefore, by definition, f is 1-1 on its domain
Find f − 1 ( x ) f^{-1}(x) f − 1 ( x ) and hence find the range of f f f
bdg-success Solution To find f − 1 ( x ) f^{-1}(x) f − 1 ( x ) , we write x = f ( y ) x=f(y) x = f ( y ) and solve for y y y
Then we will have y = f − 1 ( x ) y=f^{-1}(x) y = f − 1 ( x )
x &= \frac{2y+1}{y-1}\\
x(y-1) &= 2y + 1\\
xy-x &= 2y + 1\\
xy-2y &= x + 1\\
y(x-2) &= x + 1\\
y &= \frac{x + 1}{x-2} = f^{-1}(x)\\
Thus d o m ( f − 1 ) = r a n g e ( f ) = \Set x ∈ R ∣ x ≠ 2 = R \ \Set 2 dom(f^{-1})=range(f)=\Set{x\in\Bbb{R}\mid x\ne 2}=\Bbb{R}\backslash\Set{2} d o m ( f − 1 ) = r an g e ( f ) = \Set x ∈ R ∣ x = 2 = R \ \Set 2
Note
( f − 1 ∘ f ) ( x ) = x (f^{-1}\circ f)(x) = x ( f − 1 ∘ f ) ( x ) = x Algebraic Functions
We all have seen the concept of taking the square root of a positive number
Formally, the square root is a fractional power
We write x \sqrt{x} x to mean x 1 2 x^{\frac{1}{2}} x 2 1
nth Root Function
Let x ∈ R x\in\Bbb{R} x ∈ R We define, for n = 2 , 3 , ⋯ n=2,3,\cdots n = 2 , 3 , ⋯
y = x 1 n y=x^{\frac{1}{n}} y = x n 1 iff x = y n x=y^n x = y n
Then y = x 1 n y=x^{\frac{1}{n}} y = x n 1 is called the nth root function, n = 2 , 3 , ⋯ n=2,3,\cdots n = 2 , 3 , ⋯
The first thing we must do is determine for what values of x ∈ R x\in\Bbb{R} x ∈ R this formulation makes sense, ie what is d o m ( x 1 n ) dom(x^{\frac{1}{n}}) d o m ( x n 1 )
When n n n is even, n = 2 k n=2k n = 2 k , then y = x 1 n = x 1 2 k y=x^{\frac{1}{n}}=x^{\frac{1}{2k}} y = x n 1 = x 2 k 1 iff
x = y 2 k = ( y k ) 2 ≥ 0 , ∀ y ∈ R x=y^{2k}=(y^k)^2\ge 0,\ \forall y\in\Bbb{R} x = y 2 k = ( y k ) 2 ≥ 0 , ∀ y ∈ R
Thus f ( x ) = x 1 n f(x)=x^{\frac{1}{n}} f ( x ) = x n 1 is defined only for x ≥ 0 x\ge 0 x ≥ 0 when n is even
we don't have this restriction when n n n is odd
thus,
d o m ( x 1 n ) = { [ 0 , + ∞ ) if n even, n>0 R if n odd, n > 0
dom(x^{\frac{1}{n}})=
\begin{cases}
&[0,+\infty)\text{ if n even, n>0}\\
&\Bbb{R}\text{ if $n$ odd, $n$ > 0}
\end{cases}
d o m ( x n 1 ) = { [ 0 , + ∞ ) if n even, n>0 R if n odd, n > 0 This situation is explained easily using the graphs of the functions g ( x ) = x n g(x)=x^n g ( x ) = x n and notice that f ( x ) = x 1 n f(x)=x^{\frac{1}{n}} f ( x ) = x n 1 is the inverse function of g ( x ) g(x) g ( x )
The graph of y = x n y=x^n y = x n for the two difference cases n n n even and n n n odd makes a difference in the graph shape, for even.
With the graph just by applying horizontal line test we know right away that the function is 1-1
We see that x n x^n x n , n n n odd is invertible ∀ x ∈ R \forall x\in\Bbb{R} ∀ x ∈ R
x n x^n x n , n even invertible on [ 0 , + ∞ ) [0,+\infty) [ 0 , + ∞ ) , or ( − ∞ , 0 ] (-\infty,0] ( − ∞ , 0 ]
Thus we also have
When n n n is even ( x n ) 1 n = ∣ x ∣ , ∀ x ∈ R (x^n)^\frac{1}{n} = |x|,\ \forall x\in\Bbb{R} ( x n ) n 1 = ∣ x ∣ , ∀ x ∈ R Why is this? Think when x 2 = ∣ x ∣ \sqrt{x^2} = |x| x 2 = ∣ x ∣
( x 1 n ) n = x , ∀ x ∈ R n o d d (x^\frac{1}{n})^n = x,\ \forall x\in\Bbb{R}\ n\ odd ( x n 1 ) n = x , ∀ x ∈ R n o dd
∀ x ∈ [ 0 , + ∞ ) , n e v e n \forall x\in[0,+\infty),n\ even ∀ x ∈ [ 0 , + ∞ ) , n e v e n
The general rule is stated that you can't take even fractional roots of negative numbers in practice we restrict the domain
Other Rational Powers of x
Let r = p q > 0 r=\frac{p}{q}>0 r = q p > 0 where p p p , q q q are integers, no common divisors, q ≠ 0 q\ne 0 q = 0
We define y = x r = ( x p ) 1 q y=x^r=(x^p)^{\frac{1}{q}} y = x r = ( x p ) q 1 or y = x p q y=x^{\frac{p}{q}} y = x q p iff y q = x p y^q=x^p y q = x p
In general, to avoid problems, we will require that x ≥ 0 x\ge 0 x ≥ 0 , to take natural powers, r > 0 r>0 r > 0 ie d o m ( x r ) = [ 0 , + ∞ ) dom(x^r)=[0,+\infty) d o m ( x r ) = [ 0 , + ∞ )
When r < 0 r<0 r < 0 , we write r − t , t > 0 r-t, t>0 r − t , t > 0 and define x r = x − t = 1 x t x^r=x^{-t}=\frac{1}{x^t} x r = x − t = x t 1
Now,
d o m ( x r ) = { [ 0 , + ∞ ) , r > 0 [ 0 , + ∞ ) , r < 0
dom(x^r)=
\begin{cases}
&[0,+\infty),r>0\\
&[0,+\infty),r<0\\
\end{cases}
d o m ( x r ) = { [ 0 , + ∞ ) , r > 0 [ 0 , + ∞ ) , r < 0 r r r rational, r ∉ Z r\notin\Bbb{Z} r ∈ / Z , with the exception noted before that
d o m ( x 1 n ) = { R , n positive odd integer R \ \Set 0 , n negative odd integer
dom(x^{\frac{1}{n}})=
\begin{cases}
&\Bbb{R},\text{ $n$ positive odd integer}
&\Bbb{R}\backslash\Set{0},\text{n negative odd integer}
\end{cases}
d o m ( x n 1 ) = { R , n positive odd integer R \ \Set 0 , n negative odd integer Functions like x 1 n , x r x^{\frac{1}{n}},x^r x n 1 , x r are special cases of a type of function called algebraic
An algebraic function is one that only has rational combinations of rational powers of polynomials
bdg-secondary Example Of a Algebraic Function
f ( x ) = x + 1 x + x 3 2 f(x)=\sqrt{\frac{x+1}{x+x^{\frac{3}{2}}}} f ( x ) = x + x 2 3 x + 1
bdg-info Formal definition
y ( x ) y(x) y ( x ) is an albraic function iff ∃ \exists ∃ polynomials p 0 ( x ) , ⋯ , p t ( x ) p_0(x),\cdots ,p_t(x) p 0 ( x ) , ⋯ , p t ( x ) such that y ( x ) y(x) y ( x ) satisfies the equation t ∈ Z + t\in\Bbb{Z}^+ t ∈ Z +
p t ( x ) y t + p t − 1 ( x ) y t − 1 + ⋯ + p 1 ( x ) y + p 0 ( x ) = 0 p_t(x)y^t+p_{t-1}(x)y^{t-1}+\cdots +p_1(x)y+p_0(x) = 0 p t ( x ) y t + p t − 1 ( x ) y t − 1 + ⋯ + p 1 ( x ) y + p 0 ( x ) = 0
bdg-secondary Example Of a Algebraic Function
Just like previous example
[f(x)]^2&=\frac{x+1}{x+x^{\frac{3}{2}}}\\
(x+x^{3/2})f^2 &= x+1\\
x^{3/2}f^2 &= (x+1)-xf^2\\
x^3f^4&=[(x+1)-xf^2]^2\\
&=(x+1)^2-2x(x+1)f^2+x^2f^4\\
(x^3-x^2)f^4 + 2x(x+1)f^2-(x+1)^2&=0\\
p_4 =&\ x^3-x^2,\\
p_3 =&\ 0,\\
p_2 =&\ 2x(x+1),\\
p_1 =&\ 0,\\
p_0 =&\ -(x+1)^2\\
The functions defined on R \Bbb{R} R that we have looked so far are all algebraic
We have \Set p o l y n o m i a l s ⊆ \Set r a t i o n a l f u n c t i o n s ⊆ \Set a l g e b r a i c f u n c t i o n s \Set{polynomials}\subseteq\Set{rational\ functions}\subseteq\Set{algebraic\ functions} \Set p o l y n o mia l s ⊆ \Set r a t i o na l f u n c t i o n s ⊆ \Set a l g e b r ai c f u n c t i o n s
All other types of functions defined on R \Bbb{R} R or parts of it are called transcendental functions
Examples of these types of functions are the trigonometric functions ( sin x , cos x , tan x , sec x , csc x , cot x ) (\sin x,\cos x,\tan x,\sec x, \csc x, \cot x) ( sin x , cos x , tan x , sec x , csc x , cot x ) and their inverses bdg-warning not discussed in this course
Exponential Functions and their inverses ie logarithms and many more
The first function n ! n! n ! can be considered to be the values of the transcendental function Γ ( x ) \Gamma(x) Γ ( x ) Gamma Function when x x x is an integer, and thus is essentially a transcendental function
In fact, Γ ( n + 1 ) = n ! \Gamma(n+1) = n! Γ ( n + 1 ) = n ! bdg-danger Don't need to know this
Γ ( z ) = ∫ 0 + ∞ t z − 1 e − t d t \Gamma(z)=\int_0^{+\infty}t^{z-1}e^{-t}dt Γ ( z ) = ∫ 0 + ∞ t z − 1 e − t d t Exponential Functions and Logarithms
Let b ∈ R , b > 1 b\in\Bbb{R}, b>1 b ∈ R , b > 1 For every rational number x x x we can define b x b^x b x as we have seen before
The function y = b x y=b^x y = b x is called the exponential function with base b b b
We can extent the definition of b x b^x b x to al real values of x by a process called definition by continuity
We note some facts about real and rational numbers
Every irrational number can be approximated to any accuracy by a rational number
The formal way to say this is:
Every irrational number is the limit of a sequence of rational numbers ordered
A sequence is a subset \Set a 1 , a 2 , ⋯ , a n , ⋯ = a n n = 1 ∞ \Set{a_1, a_2, \cdots,a_n,\cdots}={a_n}^\infty_{n=1} \Set a 1 , a 2 , ⋯ , a n , ⋯ = a n n = 1 ∞ order matters
If a ∈ R \ Q = Q c = a\in\Bbb{R}\backslash\Bbb{Q}=\Bbb{Q}^c= a ∈ R \ Q = Q c = irrational numbers
then ∃ \Set a n n = 1 ∞ ⊆ Q \exists\Set{{a_n}^\infty_{n=1}}\subseteq\Bbb{Q} ∃ \Set a n n = 1 ∞ ⊆ Q such that x = lim n → + ∞ a n x=\lim_{n\to +\infty}a_n x = lim n → + ∞ a n
We then define b x = lim n → + ∞ ( b a n ) b^x=\lim_{n\to +\infty}(b^{a_n}) b x = lim n → + ∞ ( b a n )
In practical terms, to evaluate b x b^x b x , x x x irrational take a rational number, r, very close to x and evaluate b r b^r b r and say that effectively this is b x b^x b x . How close r r r must be to x x x depends on b b b and the degree of accuracy required
Traditionally a commonly base was 10, ie y = 1 0 x y=10^x y = 1 0 x Today, due to influence of computer science, y = 2 x y=2^x y = 2 x is being used more and more
There is a special base, e e e = Euler's number is in y = e x y=e^x y = e x that arises from calculus
e=\sum_{k=0}^{+\infty}\frac{1}{k!}&=1+ \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \cdots\\
&=1+1+\frac{1}{2}+ \frac{1}{6} + \frac{1}{24} + \cdots\\
&= 2.718281882845904523535360287471352662497757\cdots
e e e is a irrational number
In fact e e e is a special type of irrational number called transcendental
From graph we see exponential functions are 1-1 hence they have a inverse
Properties of Exponential Functions
b^xb^y&=b^{x+y}\\
\frac{b^x}{b^y}&=b^{x-y}\\
(b^x)^y&=b^{xy}\\
b^{-x}&=\frac{1}{b^x}\\
b^0&=1\\
Logarithms
y = b a ⟺ l o g b ( y ) = a y = b^a \iff log_b(y) = a y = b a ⟺ l o g b ( y ) = a Properties of Logarithms
l o g b ( x y ) = l o g b x + l o g b y log_b(xy)= log_bx +log_by l o g b ( x y ) = l o g b x + l o g b y
l o g b ( x n ) = n log b x , ∀ n ∈ R log_b(x^n) = n\log_bx, \forall n \in \Bbb{R} l o g b ( x n ) = n log b x , ∀ n ∈ R
In particular log b ( 1 x ) = − log b ( x ) \log_b(\frac{1}{x})=-\log_b(x) log b ( x 1 ) = − log b ( x )
bdg-secondary Proof 1
Let\ z &= log_b(xy), a=log_b(x), v+log_b(y)\\
Then\\
b^z&=xy\ and
b^u &= x\\
b^v&=y\\
so\ b^z&=xy=b^ub^v=b^{u+v}
and since the exponential function is 1-1
this tells us that z = u + v z=u+v z = u + v
ie,
l o g b ( x y ) = l o g b x + l o g b y log_b(xy) = log_bx +log_by l o g b ( x y ) = l o g b x + l o g b y
bdg-secondary Proof 2
Let\ u &= log_b(\frac{1}{x}), v=log_b(x)\\
Then\ b^u&=\frac{1}{x}\ , b^v = x
b^\frac{1}{u} &= x\\
b^{-u}&=x\\
\therefore -u=v\ or\ u=-v\\
ie\ log_b(1/x)=-;pg_b(x)\\
We now use the previous proof repeatedly to get the result ∀ n ∈ Z \forall n\in\Bbb{Z} ∀ n ∈ Z then ∀ n ∈ Q \forall n\in\Bbb{Q} ∀ n ∈ Q and then by continuity for ∀ n ∈ R \forall n\in\Bbb{R} ∀ n ∈ R
l o g b ( x n ) = n log b x log_b(x^n) = n\log_bx l o g b ( x n ) = n log b x Change of Base
Let l o g a ( x ) = z log_a(x)=z l o g a ( x ) = z then x = a z x=a^z x = a z so that l o g b ( x ) = l o g b ( a z ) = z log b ( a ) log_b(x)=log_b(a^z)=z\log_b(a) l o g b ( x ) = l o g b ( a z ) = z log b ( a ) or
l o g a ( x ) = l o g b ( x ) l o g b ( a ) log_a(x)=\frac{log_b(x)}{log_b(a)} l o g a ( x ) = l o g b ( a ) l o g b ( x ) Additional Proof
Suppose l o g 2 3 = p q , ( p , q ) > 0 log_23=\frac{p}{q},(p,q)>0 l o g 2 3 = q p , ( p , q ) > 0
3 = 2 p q 3=2^{\frac{p}{q}} 3 = 2 q p or 3 q = 2 p 3^q=2^p 3 q = 2 p
This is impossible since 3 q 3^q 3 q is odd and 2 p 2^p 2 p is even
Now
2 log 2 3 = ( 2 1 2 ) l o g 2 3 = 2 1 2 log 2 3 = 2 l o g 2 3 = 3 \sqrt{2}^{\log_23}=(2^{\frac{1}{2}})^{log_23}=2^{\frac{1}{2}\log_23}=2{log_2\sqrt{3}}=\sqrt{3} 2 l o g 2 3 = ( 2 2 1 ) l o g 2 3 = 2 2 1 l o g 2 3 = 2 l o g 2 3 = 3 which is irrational
Now 2 l o g 2 3 2log_23 2 l o g 2 3 is also irrational and ( 2 ) 2 l o g 2 3 = ( 2 2 ) 2 l o g 2 3 = 2 l o g 2 3 = 3 (\sqrt{2})^{2log_23}=(\sqrt{2}^2)^{2log_23}=2^{log_23}=3 ( 2 ) 2 l o g 2 3 = ( 2 2 ) 2 l o g 2 3 = 2 l o g 2 3 = 3
Thus ( i r r a t i o n a l ) i r r a t i o n a l (irrational)^{irrational} ( i rr a t i o na l ) i rr a t i o na l can be irrational or rational
The number ( 2 ) 2 (\sqrt{2})^{\sqrt{2}} ( 2 ) 2 is the square root of Hilbert's number 2 2 2^{\sqrt{2}} 2 2 and the head part is to show 2 2 2^{\sqrt{2}} 2 2 is irrational
Floor and Ceiling Function
The functions are important in discrete mathematics because they take a continuous variable x x x and turn it into a discrete integer variable
The functions rounds down to the nearest integer while the ceiling functions rounds up to the nearest integer
Floor Function
⌊ x ⌋ \lfloor x\rfloor ⌊ x ⌋ Largest Integer less than or equal to x x x
This is called the greatest integer function or the integer part of x and is written [ x ] [x] [ x ]
Ceiling Function
⌈ x ⌉ \lceil x\rceil ⌈ x ⌉ Smallest Integer greater than or equal to x x x
Because of how these look graphed, floor and ceiling functions are called step functions
Growth of Functions
Here we are concerned with the behavior of functions for very large values of the variable that is we consider
lim x → + ∞ f ( x ) o r lim x → − ∞ f ( x ) \lim_{x\to +\infty}f(x)\ or\ \lim_{x\to -\infty}f(x) x → + ∞ lim f ( x ) or x → − ∞ lim f ( x ) To do this we need our functions to be defined in a neighborhood of infinity
If we consider the limit at + ∞ +\infty + ∞ , then the d o m ( f ) dom(f) d o m ( f ) must contain an interval of the form [ a , + ∞ ) = \Set x ∈ R ∣ x ≥ a [a,+\infty)=\Set{x\in\Bbb{R}\mid x\ge a} [ a , + ∞ ) = \Set x ∈ R ∣ x ≥ a
If we are considering the limit at − ∞ -\infty − ∞ , then d o m ( f ) dom(f) d o m ( f ) must contain an interval of the form ( − ∞ , a ] = \Set x ∈ R ∣ x ≤ a (-\infty,a]=\Set{x\in\Bbb{R}\mid x\le a} ( − ∞ , a ] = \Set x ∈ R ∣ x ≤ a
Rates of growth
Big O notation
Here we are comparing the rate of growth at ∞ \infty ∞ of two functions.
We will state all our results for functions defined in a neighborhood of + ∞ +\infty + ∞ , We can easily state similar results fir − ∞ -\infty − ∞ . We do this because in computer science one uses these result to analyze the complexity of algorithm
Let f ( x ) f(x) f ( x ) and g ( x ) g(x) g ( x ) be defined in a neighborhood of + ∞ +\infty + ∞ . That is, for some
a\in\Bbb{R}, [a,+\infty)\subseteq\ &dom(f)\\
[a,+\infty)\subseteq\ &dom(g)\\
or\\
[a,+\infty)\subseteq\ &dom(f)\cap dom(g)
We say f ( x ) is Big O g ( x ) a s x → + ∞ f(x)\text{ is Big O }g(x)\ as\ x\to +\infty f ( x ) is Big O g ( x ) a s x → + ∞ and write f ( x ) = O ( g ( x ) ) f(x)=O(g(x)) f ( x ) = O ( g ( x )) if
∃ r e a l n u m b e r ( k , C ) , k ≥ a , C > 0 \exists\ real \ number\ (k,C), k\ge a, C>0 ∃ re a l n u mb er ( k , C ) , k ≥ a , C > 0
such stat ∣ f ( x ) ∣ ≤ C ∣ g ( x ) ∣ , ∀ x ≥ k |f(x)|\le C|g(x)|,\forall x\ge k ∣ f ( x ) ∣ ≤ C ∣ g ( x ) ∣ , ∀ x ≥ k
We also say f is dominated by g
The numbers k k k ,C C C are called witnesses to f ( x ) = O ( g ( x ) ) f(x)=O(g(x)) f ( x ) = O ( g ( x ))
Note
If one pair ( k , C ) (k,C) ( k , C ) witness f ( x ) = O ( g ( x ) ) f(x)=O(g(x)) f ( x ) = O ( g ( x )) then ( k , C ) (k,C) ( k , C ) are also witnesses for all k 1 > k k_1>k k 1 > k , C 1 > C C_1>C C 1 > C
bdg-secondary Example Let f ( x ) = 4 x 3 + 2 x 2 , g ( x ) = x 3 f(x)=4x^3+2x^2,\ g(x)=x^3 f ( x ) = 4 x 3 + 2 x 2 , g ( x ) = x 3 then f ( x ) = O ( g ( x ) ) f(x)=O(g(x)) f ( x ) = O ( g ( x )) or f ( x ) = O ( x 3 ) f(x)=O(x^3) f ( x ) = O ( x 3 )
bdg-danger Proof
Since d o m ( f ) = d o m ( g ) = R dom(f) = dom(g) = \Bbb{R} d o m ( f ) = d o m ( g ) = R , each contains neighborhood of + ∞ +\infty + ∞
Now, when x ≥ 1 x\ge 1 x ≥ 1 , 4 x 3 + 2 x 2 ≤ 4 x 3 + 2 x 3 = 6 x 3 4x^3+2x^2\le 4x^3 +2x^3 =6x^3 4 x 3 + 2 x 2 ≤ 4 x 3 + 2 x 3 = 6 x 3
since for x ≥ 1 , x 2 ≤ x 3 x\ge 1,\ x^2\ \le x^3 x ≥ 1 , x 2 ≤ x 3
Thus for x ≥ 1 x\ge 1 x ≥ 1 ,
∣ f ( x ) ∣ = 4 x 3 + 2 x 2 ≤ 6 ∣ g ( x ) ∣ = 6 x 3 + f ( x ) = O ( x 3 ) |f(x)|=4x^3+2x^2\le 6|g(x)| = 6x^3 + f(x)= O(x^3) ∣ f ( x ) ∣ = 4 x 3 + 2 x 2 ≤ 6∣ g ( x ) ∣ = 6 x 3 + f ( x ) = O ( x 3 ) here the witnesses are ( k , C ) = ( 1 , 6 ) (k, C) = (1,6) ( k , C ) = ( 1 , 6 )
Note
for x ≥ 1 , g ( x ) = O ( f ( x ) ) x\ge 1,\ g(x)=O(f(x)) x ≥ 1 , g ( x ) = O ( f ( x )) since x 3 ≤ 4 x 3 + 2 x 2 x^3\le 4x^3+2x^2 x 3 ≤ 4 x 3 + 2 x 2
In this case f = O ( g ) + g = O ( f ) f=O(g) + g=O(f) f = O ( g ) + g = O ( f )
If this is so, we say that f + g f+g f + g have the same order of growth
Note also, for x ≤ 1 x\le 1 x ≤ 1 , f ( x ) = 4 x 3 + 2 x 2 ≤ 6 x 3 ≤ 6 x 4 f(x) = 4x^3+2x^2\le 6x^3\le 6x^4 f ( x ) = 4 x 3 + 2 x 2 ≤ 6 x 3 ≤ 6 x 4
so
f ( x ) = O ( x 4 ) f(x)=O(x^4) f ( x ) = O ( x 4 ) also
This raises the general question of what is the best big O estimate for a function
bdg-info Definition
A function f ( x ) f(x) f ( x ) defined on a neighborhood of infinity is called bounded at infinity if f ( x ) ≤ C , ∀ x ≥ k f(x)\le C, \forall x\ge k f ( x ) ≤ C , ∀ x ≥ k
We write f ( x ) = O ( 1 ) a s x → + ∞ f(x) = O(1)\ as\ x\to +\infty f ( x ) = O ( 1 ) a s x → + ∞
Example:
sin x = O ( 1 ) a s x → + ∞
\sin x=O(1)\ as\ x\to +\infty
sin x = O ( 1 ) a s x → + ∞ Big O is useful in evaluating limits at infinity when g ( x ) → 0 g(x)\to 0 g ( x ) → 0 as x → + ∞ x\to +\infty x → + ∞ since if f ( x ) = O ( g ) f(x)=O(g) f ( x ) = O ( g ) we have ∣ f ( x ) ∣ ≤ C ∣ g ( x ) ∣ → 0 a s x → + ∞ |f(x)|\le C|g(x)|\to 0\ as\ x\to +\infty ∣ f ( x ) ∣ ≤ C ∣ g ( x ) ∣ → 0 a s x → + ∞ so f ( x ) → 0 f(x)\to 0 f ( x ) → 0 as x → + ∞ x \to +\infty x → + ∞ , as well
Theorem
Let f ( x ) f(x) f ( x ) be a polynomial of degree k k k
Then f ( x ) = O ( x k ) a s c → + ∞ f(x)=O(x^k)\ as\ c\to +\infty f ( x ) = O ( x k ) a s c → + ∞
bdg-danger Proof
Let f ( x ) = a k x k + a k − 1 x k − 1 + ⋯ + a 1 x + a 0 , w h e r e a k ≠ 0 f(x)=a_kx^k+a_{k-1}x^{k-1}+\cdots + a_1x + a_0,\ where\ a_k\ne 0 f ( x ) = a k x k + a k − 1 x k − 1 + ⋯ + a 1 x + a 0 , w h ere a k = 0
Then for x ≥ 1 x\ge 1 x ≥ 1 , ∣ x ∣ l ≤ ∣ x ∣ k , f o r l = 0 , 1 , ⋯ , k − 1 |x|^l\le |x|^k,\ for\ l=0,1,\cdots ,k-1 ∣ x ∣ l ≤ ∣ x ∣ k , f or l = 0 , 1 , ⋯ , k − 1 also ∣ x ∣ l = ∣ x ∣ k , ∀ x , ∀ l |x|^l=|x|^k,\forall x,\forall l ∣ x ∣ l = ∣ x ∣ k , ∀ x , ∀ l
The triangle inequality for absolute values says
∣ a + b ∣ ≤ ∣ a ∣ + ∣ b ∣ , ∀ a , b ∈ R |a+b|\le |a|+|b|,\ \forall a, b\in\Bbb{R} ∣ a + b ∣ ≤ ∣ a ∣ + ∣ b ∣ , ∀ a , b ∈ R This is easily generalized to any finite sum of numbers:
∣ b 1 + ⋯ + b n ∣ ≤ ∣ b 1 ∣ + ⋯ + ∣ b n ∣ |b_1+\cdots +b_n|\le |b_1|+\cdots +|b_n| ∣ b 1 + ⋯ + b n ∣ ≤ ∣ b 1 ∣ + ⋯ + ∣ b n ∣ Now for x ≥ 1 x\ge 1 x ≥ 1 ,
|f(x)| &= | a_k x^k + \cdots + a_0 |\\
&\le | a_k | | x^k| + \cdots + | a_1 | | x| + |a_0|\\
&= (|a_k| + \cdots + |a_0|) |x^k| =C|x^k|
Thus, f ( x ) = O ( x k ) f(x)=O(x^k) f ( x ) = O ( x k ) as x → + ∞ x\to +\infty x → + ∞ whenever f f f a polynomial of degree k k k
DirectiveParsingError:
1 argument(s) required, 0 supplied
---
{bdg-primary}`Corollary`
{bdg-danger}`Proof`
If $f(x)$ is a polynomial of degree $k$, then $f(x)=0(x^l),\forall l/ge 1$ and the result follows immediately from above inequality for $|f(x)|, x\ge 1$
We return to the question of big O estimate
First consider what it means for f ( x ) f(x) f ( x ) to be not O ( g ( x ) ) O(g(x)) O ( g ( x ))
To do this we formally negate the definition of f ( x ) = O ( g ( x ) ) f(x)=O(g(x)) f ( x ) = O ( g ( x )) as x → + ∞ x\to +\infty x → + ∞
¬ ( ∃ k , ∃ C > 0 x ≥ k → ∣ f ( x ) ∣ ≤ C ∣ g ( x ) ) ≡ ∀ k , ∀ C > 0 , ∣ f ( x 0 ) ∣ > C ∣ g ( x ) ∣ f o r s o m e x 0 ≥ k
\neg (\exists k, \exists C > 0\ \ \ x\ge k\to |f(x)|\le C|g(x))\\
\equiv\forall k, \forall C > 0, |f(x_0)|>C|g(x)|\ for\ some\ x_0\ge k
¬ ( ∃ k , ∃ C > 0 x ≥ k → ∣ f ( x ) ∣ ≤ C ∣ g ( x )) ≡ ∀ k , ∀ C > 0 , ∣ f ( x 0 ) ∣ > C ∣ g ( x ) ∣ f or so m e x 0 ≥ k bdg-secondary Example Let f ( x ) = x 2 , g ( x ) = x f(x)=x^2\ ,\ g(x)=x f ( x ) = x 2 , g ( x ) = x
Let c > 0 c>0 c > 0 be arbitrary, then
∣ f ( x ) ∣ = ∣ x ∣ 2 > C ∣ x ∣ |f(x)|= |x|^2>C|x| ∣ f ( x ) ∣ = ∣ x ∣ 2 > C ∣ x ∣ whenever ∣ x ∣ > C |x|>C ∣ x ∣ > C , ie, x > C x>C x > C
take karbbdg-danger what , x 0 = m a x ( C + 1 , k ) x_0 = max(C + 1, k) x 0 = ma x ( C + 1 , k )
Thus ∣ f ( x 0 ) ∣ > C ∣ g ( x 0 ) ∣ |f(x_0)| > C | g(x_0) | ∣ f ( x 0 ) ∣ > C ∣ g ( x 0 ) ∣ for this x 0 x_0 x 0
So, x 2 x^2 x 2 is not O ( x ) O(x) O ( x )
Theorem
Let f ( x ) = O ( g ( x ) ) f(x)=O(g(x)) f ( x ) = O ( g ( x )) as x → + ∞ x\to +\infty x → + ∞
and let g ( x ) = O ( h ( x ) ) g(x)=O(h(x)) g ( x ) = O ( h ( x )) as x → + ∞ x\to +\infty x → + ∞
then f ( x ) f(x) f ( x ) is O ( h ( x ) ) O(h(x)) O ( h ( x )) as x → + ∞ x\to +\infty x → + ∞ \
bdg-secondary Proof by Definition
By Definition
∃ C 1 > 0 , k 1 such that ∣ f ( x ) ∣ ≤ C 1 ∣ g ( x ) ∣ , ∀ x > k 1 \exists C_1 > 0 , k_1\text{ such that } |f(x)|\le C_1|g(x)|, \forall x\gt k_1 ∃ C 1 > 0 , k 1 such that ∣ f ( x ) ∣ ≤ C 1 ∣ g ( x ) ∣ , ∀ x > k 1
∃ C 2 > 0 , k 2 such that ∣ g ( x ) ∣ ≤ C 2 ∣ h ( x ) ∣ , ∀ x > k 2 \exists C_2 > 0 , k_2\text{ such that } |g(x)|\le C_2|h(x)|, \forall x\gt k_2 ∃ C 2 > 0 , k 2 such that ∣ g ( x ) ∣ ≤ C 2 ∣ h ( x ) ∣ , ∀ x > k 2
thus,
∣ f ( x ) ≤ c 1 ∣ g ( x ) ∣ ≤ c 1 c 2 ∣ h ( x ) , ∀ x ≥ m a x ( k 1 , k 2 ) |f(x)\le c_1|g(x)|\le c_1c_2|h(x), \forall x \ge max(k_1, k_2) ∣ f ( x ) ≤ c 1 ∣ g ( x ) ∣ ≤ c 1 c 2 ∣ h ( x ) , ∀ x ≥ ma x ( k 1 , k 2 )
If f f f , g g g , h h h are as in theorem, and suppose h ( x ) h(x) h ( x ) is not O ( g ( x ) ) O(g(x)) O ( g ( x )) , then we say that g ( x ) g(x) g ( x ) provides a better O estimate of f ( x ) f(x) f ( x ) than h ( x ) h(x) h ( x ) does
If f ( x ) = O ( g ( x ) ) a n d h ( x ) i s n o t O ( g ( x ) ) ∀ h ( x ) s u c h t h a t f ( x ) = O ( h ( x ) ) f(x)=O(g(x))\ and\ h(x)\ is\ not\ O(g(x)) \forall h(x)\ such\ that\ f(x)=O(h(x)) f ( x ) = O ( g ( x )) an d h ( x ) i s n o t O ( g ( x )) ∀ h ( x ) s u c h t ha t f ( x ) = O ( h ( x ))
then we call f ( x ) = O ( g ( x ) ) a s x → + ∞ f(x)=O(g(x))\ as\ x\to +\infty f ( x ) = O ( g ( x )) a s x → + ∞
The best O-estimate of f ( x ) f(x) f ( x ) as x → + ∞ x\to +\infty x → + ∞
The best O-estimate is an awkward concept to deal with and even stull only gives upper bounds for growth
bdg-secondary Example 1 let f ( n ) = n ! f(n) = n! f ( n ) = n !
then n ! = 1 ⋅ 2 ⋅ 3 ⋯ n ≤ n ⋅ n ⋯ n = n n n! = 1\cdot 2 \cdot 3 \cdots n \le n \cdot n \cdots n = n^n n ! = 1 ⋅ 2 ⋅ 3 ⋯ n ≤ n ⋅ n ⋯ n = n n
thus n ! = O ( n n ) n! = O(n^n) n ! = O ( n n ) as n → + ∞ n\to +\infty n → + ∞
bdg-secondary Example 2 Let f b ( n ) = l o g b n , b > 1 f_b(n) = log_bn, b> 1 f b ( n ) = l o g b n , b > 1
Now it is easily shown that n < 2 n , ∀ n ≥ 1 n<2^n, \forall n\ge 1 n < 2 n , ∀ n ≥ 1
l o g 2 ( n ) < l o f 2 ( 2 n ) = n log_2(n) < lof_2(2^n) = n l o g 2 ( n ) < l o f 2 ( 2 n ) = n
and, using change of base formula for logarithms
l o g b n = l o g 2 n l o g 2 b < 1 l o g 2 k ⋅ n log_bn = \frac{log_2n}{log_2b}<\frac{1}{log_2k}\cdot n l o g b n = l o g 2 b l o g 2 n < l o g 2 k 1 ⋅ n so l o g b ( n ) = O ( n ) log_b(n) = O(n) l o g b ( n ) = O ( n ) as n → + ∞ n\to +\infty n → + ∞ for any base b > 1 b>1 b > 1
bdg-primary Theorem 3 Let f 1 ( x ) = O ( g 1 ( x ) ) , f 2 ( x ) = O ( g 2 ( x ) ) f_1(x)=O(g_1(x)), f_2(x)=O(g_2(x)) f 1 ( x ) = O ( g 1 ( x )) , f 2 ( x ) = O ( g 2 ( x )) as x → + ∞ x\to +\infty x → + ∞
Then\
a) f 1 ( x ) + f 2 ( x ) = O ( m a x ( ∣ g 1 ( x ) ∣ , ∣ g 2 ( x ) ∣ ) ) f_1(x) + f_2(x) = O(max(|g_1(x)|, |g_2(x)|)) f 1 ( x ) + f 2 ( x ) = O ( ma x ( ∣ g 1 ( x ) ∣ , ∣ g 2 ( x ) ∣ )) as x → + ∞ x\to +\infty x → + ∞
bdg-secondary Proof
|f_1(x) + f_2(x)| &\subseteq |f_1(x)| + |f_2(x)|\\
&\subseteq C_1|g_1(x)| + C_2|g_2(x)|\\
&\subseteq (C_1 + C_2)\ \max(|g_1(x)|,|g_2(x)|)\ \forall x\ \ge \max(k_1,k_2)
b) f 1 ( x ) ⋅ f 2 ( x ) = O ( g 1 ( x ) ⋅ g 2 ( x ) ) f_1(x) \cdot f_2(x) = O(g_1(x)\cdot g_2(x)) f 1 ( x ) ⋅ f 2 ( x ) = O ( g 1 ( x ) ⋅ g 2 ( x )) as x → + ∞ x\to +\infty x → + ∞
bdg-secondary Proof
|f_1(x)f_2(x)| &= |f_1(x)| \cdot |f_2(x)|\\
&\le C_1|g_1(x)| \cdot C_2|g_2(x)|\\
&\subseteq (C_1C_2)|g_1(x)\cdot g_2(x)|\\
\\
\forall x \ge \max (k_1, k_2)
bdg-success Corollary Let f 1 ( x ) = O ( g ( x ) ) + f 2 ( x ) = O ( g ( x ) ) f_1(x)=O(g_(x)) + f_2(x)=O(g(x)) f 1 ( x ) = O ( g ( x )) + f 2 ( x ) = O ( g ( x )) as x → + ∞ x\to +\infty x → + ∞
Then,
a) f 1 ( x ) + f 2 ( x ) = O ( g ( x ) ) f_1(x) +f_2(x) = O(g(x)) f 1 ( x ) + f 2 ( x ) = O ( g ( x )) as x → + ∞ x\to +\infty x → + ∞
b) f 1 ( x ) ⋅ f 2 ( x ) = O ( g 2 ( x ) ) f_1(x)\cdot f_2(x) = O(g^2(x)) f 1 ( x ) ⋅ f 2 ( x ) = O ( g 2 ( x )) as x → + ∞ x\to +\infty x → + ∞
bdg-secondary Example Let f ( n ) = 3 n ln ( n ! ) + ( n 2 + 3 ) ln n f(n) = 3n \ln(n!) + (n^2 + 3)\ln n f ( n ) = 3 n ln ( n !) + ( n 2 + 3 ) ln n
We have ln ( n ! ) ≤ ln ( n n ) = n ln n \ln (n!) \le \ln(n^n) = n\ln n ln ( n !) ≤ ln ( n n ) = n ln n so ln ( n ! ) = O ( n ln n ) \ln (n!) = O(n\ln n) ln ( n !) = O ( n ln n )
and so 3 n ln ( n ! ) = O ( n 2 ln n ) 3n\ln (n!) = O(n^2\ln n) 3 n ln ( n !) = O ( n 2 ln n ) by theorem 3
also n 2 + 3 = O ( n 2 ) n^2 + 3 = O(n^2) n 2 + 3 = O ( n 2 ) by theorem 1 so
( n 2 + 3 ) ln n = O ( n 2 ln n ) (n^2 + 3)\ln n = O(n^2\ln n) ( n 2 + 3 ) ln n = O ( n 2 ln n )
∴ f ( n ) = O ( n 2 ln n ) \therefore f(n) = O(n^2\ln n) ∴ f ( n ) = O ( n 2 ln n ) as n → + ∞ n\to +\infty n → + ∞
bdg-secondary Exercise find a O-estimate for f ( x ) = ( x + 1 ) ln ( x 2 + 1 ) + 3 x 2 f(x)=(x+1)\ln(x_2+1) + 3x^2 f ( x ) = ( x + 1 ) ln ( x 2 + 1 ) + 3 x 2
bdg-success Hint 0 < x ln x ≤ x 2 0<x\ln x\le x^2 0 < x ln x ≤ x 2 for x > 1 x>1 x > 1
The O-estimate of a function gives an upper bound for the growth of f(x) as x → + ∞ x\to +\infty x → + ∞ (or as x → − ∞ x\to -\infty x → − ∞ )
The Ω \Omega Ω -estimate gives a lower bound for the growth of a function
Definition
We say f ( x ) = Ω ( g ( x ) ) f(x)=\Omega(g(x)) f ( x ) = Ω ( g ( x )) as x → + ∞ x\to +\infty x → + ∞ iff
∃ C > 0 , ∃ k \exists C>0, \exists k ∃ C > 0 , ∃ k such that ∣ ∣ f ( x ) ≥ C ∣ g ( x ) ∣ , ∀ x ≥ k ||f(x)\ge C|g(x)|, \forall x\ge k ∣∣ f ( x ) ≥ C ∣ g ( x ) ∣ , ∀ x ≥ k
If f ( x ) = O g ( x ) f(x) = O g(x) f ( x ) = O g ( x ) and f ( x ) = Ω ( g ( x ) ) f(x)=\Omega(g(x)) f ( x ) = Ω ( g ( x )) as x → + ∞ x\to +\infty x → + ∞ then we say that f f f and g g g have the same order of growth as x → + ∞ x\to +\infty x → + ∞ or f ( x ) f(x) f ( x ) is of order g ( x ) g(x) g ( x ) as x → + ∞ x\to +\infty x → + ∞ and we write
f(x) = \Theta(g(x))$$ as $x\to +\infty$
$f(x)=\Theta(g(x))\ iff\ f=O(g(x))\ and\ g=O(f(x))$
{bdg-secondary}`Example` $f(x)^2 + 8x \ln x$
For $x\ge 1$, we can establish the inequalities
$$0 \le 3x^2 \le 3x^2 + 8x\ln x \le 3x^2 + 8x^2 = 11x^2 Thus f ( x ) = O ( x 2 ) f(x) = O(x^2) f ( x ) = O ( x 2 ) as x → + ∞ x\to +\infty x → + ∞
and f ( x ) = Ω ( x 2 ) f(x)=\Omega(x^2) f ( x ) = Ω ( x 2 ) as x → + ∞ x\to +\infty x → + ∞
Thus f ( x ) = Θ ( x 2 ) f(x)=\Theta(x^2) f ( x ) = Θ ( x 2 ) as x → + ∞ x\to +\infty x → + ∞
To show that ln x < x , x ≥ 1 \ln x < x , x \ge 1 ln x < x , x ≥ 1 consider that
z 1 + z < ln ( 1 z ) < z f o r z > 0 \frac{z}{1+z}< \ln(1_z) < z\ \ for\ z>0 1 + z z < ln ( 1 z ) < z f or z > 0 Theorem 4
Let f ( x ) f(x) f ( x ) be a polynomial of degree k k k then f ( x ) = Θ ( x k ) f(x)=\Theta(x^k) f ( x ) = Θ ( x k ) as x → + ∞ x\to +\infty x → + ∞
bdg-danger Proof
Theorem 1 tells us that ---
Thus we must show that ∃ k , C > 0 \exists k, C>0 ∃ k , C > 0 such that ∣ f ( x ) ∣ ≥ C ∣ x ∣ k ∀ x ≥ k |f(x)|\ge C|x|^k\ \forall x\ge k ∣ f ( x ) ∣ ≥ C ∣ x ∣ k ∀ x ≥ k
Let f ( x ) = a k x k + ⋯ + a 1 x + a 0 , a l ≠ 0 f(x) = a_kx^k+\cdots +a_1x+a_0,\ a_l\ne 0 f ( x ) = a k x k + ⋯ + a 1 x + a 0 , a l = 0
L e t k > max ( 1 , 2 k m ∣ a k ∣ ) w h e r e m = max i = 0 , ⋯ , k − 1 ∣ a i ∣ Let\ k>\ \max(1, \frac{2km}{|a_k|})\ where\ m= \max_{i=0,\cdots ,k-1}|a_i| L e t k > max ( 1 , ∣ a k ∣ 2 km ) w h ere m = i = 0 , ⋯ , k − 1 max ∣ a i ∣ If x ≥ k x\ge k x ≥ k , we have
∣ f ( x ) ∣ = ∣ a k x k + ⋯ + a 1 x + a 0 ∣ = ∣ x ∣ k ∣ a k + a k − 1 x + a k − 2 x 2 + ⋯ a 1 x k − 1 + a 0 x k ∣ |f(x)|=|a_kx^k+\cdots +a_1x+a_0|\\=\\|x|^k|a_k+\frac{a_k-1}{x}+\frac{a_k-2}{x^2}+\cdots\frac{a_1}{x^k-1}+\frac{a_0}{x^k}| ∣ f ( x ) ∣ = ∣ a k x k + ⋯ + a 1 x + a 0 ∣ = ∣ x ∣ k ∣ a k + x a k − 1 + x 2 a k − 2 + ⋯ x k − 1 a 1 + x k a 0 ∣ Now
|\frac{a_{k-i}}{x^2}|&\le|\frac{a_{k-1}}{x}|\ since\ x\ge 1\\
&\le |\frac{a_{k-i}}{k}|\ since\ x\ge k\\
&\le |\frac{a_{k-i}}{(\frac{2km}{ |a_k| })}| = |\frac{a_{k-1}}{m}| \cdot \frac{|a_k|}{2k} \color{yellow}{\frac{|a_k|}{2k}\le 1\ by\ definition}\\
&\le \frac{|a_k|}{2k}
thus
− ∣ a k ∣ 2 k ≤ a k − i x i ≤ ∣ a k ∣ 2 k and thus ∣ − ∣ a k ∣ 2 ≤ a k − 1 x + ⋯ + a 0 x k ∣ ≥ ∣ a k ∣ 2 this tells us that ∣ a k + a k − 1 x + ⋯ + a 0 x k ∣ ≥ ∣ a k ∣ 2 Thus ∣ f ( x ) ∣ = ∣ x ∣ k ∣ a k + a k − 1 x + ⋯ + a 0 x k ∣ ≥ ∣ a k ∣ 2 ∣ x ∣ k = > f ( x ) = Ω ( x k ) as x → + ∞ ∴ f ( x ) = Θ ( x k ) as x → + ∞ whenever f ( x ) is a polynomial of degree k
\frac{-|a_k|}{2k} \le \frac{a_{k-i}}{x^i} \le \frac{|a_k|}{2k}\\
\text{ and thus } | \frac{-|a_k|}{2}\le \frac{a_{k-1}}{x}+\cdots +\frac{a_0}{x^k}|\ge\frac{|a_k|}{2}\\
\text{ this tells us that } |a_k + \frac{a_{k-1}}{x}+\cdots +\frac{a_0}{x^k}|\ge\frac{|a_k|}{2}\\
\text{ Thus } |f(x)| = |x|^k | a_k + \frac{a_{k-1}}{x}+\cdots +\frac{a_0}{x^k}|\ge\frac{|a_k|}{2}|x|^k\\
\\
=> f(x) = \Omega (x^k)\text{ as }x\to +\infty\\
\therefore f(x) = \Theta (x^k)\text{ as }x\to +\infty\text{ whenever $f(x)$ is a polynomial of degree $k$}
2 k − ∣ a k ∣ ≤ x i a k − i ≤ 2 k ∣ a k ∣ and thus ∣ 2 − ∣ a k ∣ ≤ x a k − 1 + ⋯ + x k a 0 ∣ ≥ 2 ∣ a k ∣ this tells us that ∣ a k + x a k − 1 + ⋯ + x k a 0 ∣ ≥ 2 ∣ a k ∣ Thus ∣ f ( x ) ∣ = ∣ x ∣ k ∣ a k + x a k − 1 + ⋯ + x k a 0 ∣ ≥ 2 ∣ a k ∣ ∣ x ∣ k => f ( x ) = Ω ( x k ) as x → + ∞ ∴ f ( x ) = Θ ( x k ) as x → + ∞ whenever f ( x ) is a polynomial of degree k